Korolev dilahirkan di Zhytomyr, ibu kota Gabenor Volhynia dari Empayar Rusia. Ayahnya, Pavel Yakovlevich Korolev, dilahirkan di Mogilev dari seorang askar Rusia dan seorang ibu Belarus. Ibunya, Maria Nikolaevna Koroleva (Moskalenko/Bulanina), adalah anak perempuan seorang saudagar kaya dari kota Nizhyn di Ukraine (yang kemudian menjadi bahagian dari Empayar Rusia), dengan warisan Caporak Zaporozhian. Ayahnya berpindah ke Zhytomyr untuk menjadi guru bahasa Rusia. Tiga tahun selepas kelahiran Sergei, pasangan itu berpisah kerana masalah kewangan. Walaupun Pavel kemudian menulis surat kepada Maria meminta pertemuan dengan anaknya, Sergei diberitahu oleh ibunya bahawa ayahnya diduga telah meninggal. Sergei tidak pernah melihat ayahnya setelah perpecahan keluarga, dan Pavel meninggal pada tahun 1929 sebelum anaknya mengetahui kebenaran.

Korolev dibesarkan di Nizhyn, di bawah jagaan datuk dan neneknya dari ibu, Mykola Yakovych Moskalenko yang merupakan peniaga Guild Kedua dan Maria Matviivna Moskalenko (Fursa), seorang anak perempuan cossack tempatan. Ibu Korolev juga mempunyai saudara perempuan Anna dan dua saudara lelaki Yuri dan Vasyl. Maria Koroleva sering pergi mengikuti kursus pendidikan tinggi Wanita di Kyiv. Semasa kecil, Korolev keras kepala, gigih, dan berhujah. Sergei membesarkan seorang anak yang kesepian dengan beberapa rakan. Korolev mula membaca pada usia dini, dan kemampuannya dalam matematik dan mata pelajaran lain menjadikannya pelajar kegemaran gurunya, tetapi menimbulkan rasa cemburu dari rakan sebayanya. Dia kemudian menyatakan dalam wawancara, penderitaan rakan sekuliah membuli dan menggodanya sebagai seorang anak kecil mendorong fokusnya pada pekerjaan akademik. Ibunya bercerai dengan Pavel pada tahun 1915 dan pada tahun 1916 mengahwini Grigory Mikhailovich Balanin, seorang jurutera elektrik yang pernah mendapat pendidikan di Jerman tetapi terpaksa menghadiri Universiti Politeknik Kiev kerana diploma kejuruteraan Jerman tidak dikenali di Rusia. Setelah mendapat pekerjaan dengan kereta api wilayah, Grigory memindahkan keluarga itu ke Odessa pada tahun 1917, di mana mereka mengalami kesukaran dengan banyak keluarga lain melalui tahun-tahun yang penuh gejolak setelah Revolusi Rusia dan perjuangan dalaman berterusan sehingga kaum Bolshevik mengambil alih kekuasaan yang tidak tertandingi pada tahun 1920. Sekolah-sekolah tempatan ditutup dan muda Korolev harus melanjutkan pelajaran di rumah. Grigory membuktikan pengaruh yang baik terhadap anak tirinya, yang menderita demam kepialu semasa kekurangan makanan pada 1919.